5832. AND Rounds

You are given a cyclic array A having n numbers. In an AND round, each element of the array A is replaced by the bitwise AND of itself, the previous element, and the next element in the array. All operations take place simultaneously. Can you calculate A after k such AND rounds?

Input. The first line contains the number of test cases t. Then follow 2t lines, 2 per test case. The first line contains two space separated integers n (3 ≤ n ≤ 20000) and k (1 ≤ k ≤ 10⁹). The next line contains n space separated integers A_i (0 ≤ A_i ≤ 10⁹), which are the initial values of the elements in array A.

Output. Print t lines, one per test case. For each test case, output a space separated list of n integers, specifying the contents of array A after k AND rounds.

Sample input

2

3 1

1 2 3

5 100

1 11 111 1111 11111

Sample output

0 0 0

1 1 1 1 1

РЕШЕНИЕ

структуры данных – дерево отрезков

Анализ алгоритма

Пусть изначально число A_i в p-ом бите содержит 0. Тогда после первого раунда числа A_i-1 и A_i+1 в p-ом бите будут содержать 0 (индексы вычисляются по модулю n). После k-го раунда числа A_i-1, …, A_i-k и A_i+1, …, A_i+k в p-ом бите будут содержать 0.

Если в p-ом бите A_i изначально находится 0, то;

· в p-ом бите A_i ни на каком раунде не появится 1;

· через k ≥ n / 2 раундов все числа массива в p-ом бите будут содержать 0.

Лемма. Если k ≥ n / 2, то для решения задачи достаточно вычислить побитовый AND всех элементов массива и вывести его n раз. Что и будет ответом.

Лемма. Если k < n / 2, то на A_i после k раундов подействуют начальные значения A_i-1, …, A_i-k и A_i+1, …, A_i+k. Если одно из них в p-ом бите содержит 0, то после k раундов A_i в в p-ом бите будет также содержать 0. Значит для ответа на вопрос достаточно вычислить побитовый AND элементов A_i-k, …, A_i, …, A_i+k. Это можно совершить за время O(log₂n), если на элементах входного массива A построить дерево отрезков, поддерживающее операцию побитового AND.

Реализация алгоритма

#include <stdio.h>

#define MAX 20010

int a[MAX];

int SegTree[4*MAX];

int tests, i, n, k, res;

int min(int i, int j)

{

return (i < j) ? i : j;

}

int max(int i, int j)

{

return (i > j) ? i : j;

}

void BuildTree(int *a, int Vertex, int Left, int Right)

{

if (Left == Right)

SegTree[Vertex] = a[Left];

else

{

int Middle = (Left + Right) / 2;

BuildTree(a, 2*Vertex, Left, Middle);

BuildTree(a, 2*Vertex+1, Middle+1, Right);

SegTree[Vertex] = SegTree[2*Vertex] & SegTree[2*Vertex+1];

}

}

int Query(int Vertex, int LeftPos, int RightPos, int Left, int Right)

{

if (Left > Right) return -1;

if ((Left == LeftPos) && (Right == RightPos)) return SegTree[Vertex];

int Middle = (LeftPos + RightPos) / 2;

return Query(2*Vertex, LeftPos, Middle, Left, min(Right,Middle)) &

Query(2*Vertex+1, Middle+1, RightPos, max(Left,Middle+1),Right);

}

int main(void)

{

scanf("%d",&tests);

while(tests--)

{

scanf("%d %d",&n,&k);

for(i = 0; i < n; i++) scanf("%d",&a[i]);

if (k >= n / 2)

{

for(res = a[0], i = 1; i < n; i++) res &= a[i];

for(i = 0; i < n; i++)

{

if (i) printf(" ");

printf("%d",res);

}

printf("\n");

continue;

}

BuildTree(a,1,0,n-1);

for(i = 0; i < n; i++)

{

int Start = (i - k + n) % n;

int End = (i + k + n) % n;

if (Start < End) res = Query(1,0,n-1,Start,End);

else res = Query(1,0,n-1,Start,n-1) & Query(1,0,n-1,0, End);

if (i) printf(" ");

printf("%d",res);

}

printf("\n");

}

return 0;

}